package fun.coding.leetcode;

public class FindMinimumInRotatedSortedArrayII {

	public static void main(String[] args) {
		FindMinimumInRotatedSortedArrayII ins = new FindMinimumInRotatedSortedArrayII();
		
		int[] t1 = {4, 5, 6, 7, 0, 1, 2};
		System.out.println(ins.findMin(t1));
		
		int[] t2 = {3, 1, 2, 2, 2};
		System.out.println(ins.findMin(t2));
		
		// Very good test cases for dup
		int[] t3 = {3, 1, 3};
		System.out.println(ins.findMin(t3));
		
		int[] t4 = {1, 1};
		System.out.println(ins.findMin(t4));
	}
	
	public int findMin(int[] num) {
		if (num == null || num.length == 0) return 0;
		
		return helper(num, 0, num.length - 1);
	}
	
	private int helper(int[] num, int left, int right) {
		if (left == right) return num[left];
		if (right == left + 1 && num[left] == num[right]) return num[left];
		
		int mid = (left + right) / 2;
		
		// Since there is only 1 rotation, there should only be 1 part that is not ordered
		if (num[left] > num[right]) {
			if (num[mid] > num[right]) {
				return helper(num, mid + 1, right);
			} else {
				return helper(num, left, mid);
			}
		} else if (num[left] < num[right]){
			// if we fall into an ordered range
			return num[left];
		} else {
			// Here I am just keep search both left, and right, thus 2^lgN = N, O(N) worst case then
			return Math.min(helper(num, left, mid), helper(num, mid, right));
		}
	}

}
